﻿#define _CRT_SECURE_NO_WARNINGS 1

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

//选择排序
void SelectionSort(int* arr, int n)
{

	//循环执行n-1次
	for (int i = 1; i < n; i++)
	{
		int min = i - 1;
		//找出最小值
		for (int j = i; j < n; j++)
		{
			if (arr[j] < arr[min])
			{
				min = j;
			}
		}
		int tmp = arr[i - 1];
		arr[i - 1] = arr[min];
		arr[min] = tmp;
	}
}

//插入排序
void InsertSort(int* arr, int n)
{
	for (int i = 0; i < n; ++i)
	{
		//记录有序序列第一个元素的下标
		int start = i;
		//待插入的元素
		int tem = arr[start];
		//单趟排
		while (start > 0)
		{
			//比插入的数小就向后移
			if (arr[start - 1] > tem)
			{
				arr[start] = arr[start - 1];
				start--;
			}
			//比插入的数大，跳出循环
			else
			{
				break;
			}
		}
		//tem放到比插入的数大的数的后面
		arr[start] = tem;
		//代码执行到此位置有两种情况:
		//1.待插入元素找到应插入位置（break跳出循环到此）
		//2.待插入元素比当前有序序列中的所有元素都大（while循环结束后到此）
	}
}

//希尔排序
void ShellSort(int* arr, int n)
{
	int gap = n;
	while (gap > 1)
	{
		//每次对gap折半操作
		gap = gap / 2;
		//单趟排序
		for (int i = 0; i < n - gap; ++i)
		{
			int end = i;
			int tem = arr[end + gap];
			while (end >= 0)
			{
				if (tem < arr[end])
				{
					arr[end + gap] = arr[end];
					end -= gap;
				}
				else
				{
					break;
				}
			}
			arr[end + gap] = tem;
		}
	}
}


//冒泡排序
void BubbleSort(int* arr, int n)
{
	for (int i = 0; i < n - 1; i++)
	{
		for (int j = 0; j < n - 1; j++)
		{
			if (arr[j] > arr[j + 1])
			{
				int tmp = arr[j];
				arr[j] = arr[j + 1];
				arr[j + 1] = tmp;
			}
		}
	}
}

//快速排序
void QuickSort(int* arr, int begin, int end)
{
	if (begin >= end)
		return;
	int left = begin, right = end;
	int key = arr[begin];
	while (begin < end)
	{
		//找小
		while (arr[end] >= key && begin < end)
		{
			--end;
		}
		//小的放到左边的坑里
		arr[begin] = arr[end];
		//找大
		while (arr[begin] <= key && begin < end)
		{
			++begin;
		}
		//大的放到右边的坑里
		arr[end] = arr[begin];
	}
	arr[begin] = key;
	int keyi = begin;
	QuickSort(arr, left, keyi - 1);
	QuickSort(arr, keyi + 1, right);
}

//调整堆
void HeapAdjust(int* arr, int start, int end)
{
	int tmp = arr[start];
	for (int i = 2 * start + 1; i <= end; i = i * 2 + 1)
	{
		if (i < end && arr[i] < arr[i + 1])//有右孩子并且左孩子小于右孩子
		{
			i++;
		}//i一定是左右孩子的最大值
		if (arr[i] > tmp)
		{
			arr[start] = arr[i];
			start = i;
		}
		else
		{
			break;
		}
	}
	arr[start] = tmp;
}

//堆排序
void HeapSort(int* arr, int len)
{
	//第一次建立大根堆，从后往前依次调整
	for (int i = (len - 1 - 1) / 2; i >= 0; i--)
	{
		HeapAdjust(arr, i, len - 1);
	}
	//每次将根和待排序的最后一次交换，然后在调整
	int tmp;
	for (int i = 0; i < len - 1; i++)
	{
		tmp = arr[0];
		arr[0] = arr[len - 1 - i];
		arr[len - 1 - i] = tmp;
		HeapAdjust(arr, 0, len - 1 - i - 1);
	}
}

int merge(int* a, int left, int mid, int right)
{
	int* arr = (int*)malloc(sizeof(int) * (right - left + 1));//创建工具数组
	int i, j, k;
	i = left;
	j = mid + 1;
	k = 0;
	while (i <= mid && j <= right)
	{
		arr[k++] = (a[i] <= a[j]) ? a[i++] : a[j++];//归并
	}
	while (i <= mid)
		arr[k++] = a[i++];
	while (j <= right)
		arr[k++] = a[j++];
	for (k = left; k <= right; k++)
	{
		a[k] = arr[k - left];
	}
	free(arr);
	return 0;
}

void MergeSort(int* a, int left, int right)
{
	if (left == right)
		return;
	int mid = left + ((right - left) >> 2);//计算中点
	MergeSort(a, left, mid);
	MergeSort(a, mid+1, right);
	merge(a, left, mid, right);
}

//基数排序
void RadixSort(int* arr, int n)
{
	//max为数组中最大值
	int max = arr[0];
	int base = 1;

	//找出数组中的最大值
	for (int i = 0; i < n; i++)
	{
		if (arr[i] > max)
		{
			max = arr[i];
		}
	}
	//循环结束max就是数组最大值


	//临时存放数组元素的空间
	int* tmp = (int*)malloc(sizeof(int) * n);
	if (!tmp)
		return;

	//循环次数为最大数的位数
	while (max / base > 0)
	{
		//定义十个桶，桶里面装的不是数据本身，而是每一轮排序对应（十、白、千...）位的个数
		//统计每个桶里面装几个数
		int bucket[10] = { 0 };
		for (int i = 0; i < n; i++)
		{
			//arr[i] / base % 10可以取到个位、十位、百位对应的数字
			bucket[arr[i] / base % 10]++;
		}
		//循环结束就已经统计好了本轮每个桶里面应该装几个数


		//将桶里面的元素依次累加起来，就可以知道元素存放在临时数组中的位置
		for (int i = 1; i < 10; i++)
		{
			bucket[i] += bucket[i - 1];
		}
		//循环结束现在桶中就存放的是每个元素应该存放到临时数组的位置


		//开始放数到临时数组tmp
		for (int i = n - 1; i >= 0; i--)
		{
			tmp[--bucket[arr[i] / base % 10]] = arr[i];
		}

		//把临时数组里面的数拷贝回去
		for (int i = 0; i < n; i++)
		{
			arr[i] = tmp[i];
		}
		base *= 10;
	}
	free(tmp);
}

//性能分析
void PerformanceAnalysis(int choice)
{
	int arr[30000] = { 0 };
	//重置文件指针
	FILE* pf = fopen("data.txt", "r");
	for (int i = 0; i < 30000; i++)
	{
		fscanf(pf, "%d", &arr[i]);//从文件中读取数据
	}
	fclose(pf);
	clock_t start, end;
	double cpu_time_used;
	switch(choice)
	{
		case 1:
			start = clock();  // 开始计时
			SelectionSort(arr, 30000);
			end = clock();  // 结束计时
			cpu_time_used = ((double)((double)end - (double)start)) / CLOCKS_PER_SEC;
			printf("选择排序程序执行时间为: %lf 秒\n", cpu_time_used);
			break;
		case 2:
			start = clock();  // 开始计时
			InsertSort(arr, 30000);
			end = clock();  // 结束计时
			cpu_time_used = ((double)((double)end - (double)start)) / CLOCKS_PER_SEC;
			printf("插入排序程序执行时间为: %lf 秒\n", cpu_time_used);
			break;
		case 3:
			start = clock();  // 开始计时
			ShellSort(arr, 30000);
			
			end = clock();  // 结束计时
			cpu_time_used = ((double)((double)end - (double)start)) / CLOCKS_PER_SEC;
			printf("希尔排序程序执行时间为: %lf 秒\n", cpu_time_used);
			break;
		case 4:
			start = clock();  // 开始计时
			BubbleSort(arr, 30000);
			end = clock();  // 结束计时
			cpu_time_used = ((double)((double)end - (double)start)) / CLOCKS_PER_SEC;
			printf("冒泡排序程序执行时间为: %lf 秒\n", cpu_time_used);
			break;
		case 5:
			start = clock();  // 开始计时
			QuickSort(arr, 0, 29999);
			end = clock();  // 结束计时
			cpu_time_used = ((double)((double)end - (double)start)) / CLOCKS_PER_SEC;
			printf("快速排序程序执行时间为: %lf 秒\n", cpu_time_used);
			break;
		case 6:
			start = clock();  // 开始计时
			HeapSort(arr, 30000);
			end = clock();  // 结束计时
			cpu_time_used = ((double)((double)end - (double)start)) / CLOCKS_PER_SEC;
			printf("堆排序程序执行时间为:   %lf 秒\n", cpu_time_used);
			break;
		case 7:
			start = clock();  // 开始计时
			MergeSort(arr, 0, 29999);
			end = clock();  // 结束计时
			cpu_time_used = ((double)((double)end - (double)start)) / CLOCKS_PER_SEC;
			printf("归并排序程序执行时间为: %lf 秒\n", cpu_time_used);
			break;
		case 8:
			start = clock();  // 开始计时
			RadixSort(arr, 30000);
			end = clock();  // 结束计时
			cpu_time_used = ((double)((double)end - (double)start)) / CLOCKS_PER_SEC;
			printf("基数排序程序执行时间为: %lf 秒\n", cpu_time_used);
			break;
	}
}

int main()
{
	srand((unsigned int)time(NULL));//定义随机数起点
	int n = 29999;
	//打开文件
	FILE* pf = fopen("data.txt", "w");
	//判断文件是否打开成功
	if (!pf)
	{
		printf("文件打开失败！\n");
	}
	while(n--)
		fprintf(pf, "%d\n", rand());//将30000个随机数字导出到文件中
	fprintf(pf, "%d", rand());
	fclose(pf);
	PerformanceAnalysis(1);
	PerformanceAnalysis(2);
	PerformanceAnalysis(3);
	PerformanceAnalysis(4);
	PerformanceAnalysis(5);
	PerformanceAnalysis(6);
	PerformanceAnalysis(7);
	PerformanceAnalysis(8);
}